import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Day6 {
    public static void main(String[] args) {
        List<String> path = new ArrayList<>();

        StringBuilder tmp = new StringBuilder(".");
        for(int i=1;i<4;i++) {
            tmp.append(".");
        }
        for(int i=0;i<4;i++) {
            path.add(tmp.toString());
        }
        path.remove(0);
        StringBuilder s = new StringBuilder(path.get(0));
         s.setCharAt(0,'Q');
        path.add(0,s.toString());
        System.out.println();
    }
    public static void main1(String[] args) {
        List<List<String>> ret = new ArrayList<>();
        List<String> path = new ArrayList<>();
        StringBuilder s = new StringBuilder(".");
        path.add("sss");
        path.add("sss");
        ret.add(path);
        path.add(0,"x");
        ret.add(path);
    }
    List<List<String>> ret = new ArrayList<>();//记录答案返回值
    List<String> path = new ArrayList<>();//存放标记的字符串
    boolean[] col;//标记列，防止同列被杀
    boolean[] dig1;//标记正对角线
    boolean[] dig2;//标记斜对角先线
    public List<List<String>> solveNQueens(int n) {
        StringBuilder tmp = new StringBuilder(".");
        for(int i=1;i<n;i++) {
            tmp.append(".");
        }
        for(int i=0;i<n;i++) {
            path.add(tmp.toString());
        }
        //走到这里，path里面存的是n个n个.的字符串
        col = new boolean[n];
        dig1 = new boolean[n*2];
        dig2 = new boolean[n*2];
        dfs(n,0);
        return ret;
    }
    public void dfs(int n,int pos) {
        if(pos == n) {
            ret.add(new ArrayList(path));
            return;
        }
        //列、正对、斜对
        for(int i=0;i<n;i++) {//遍历列
            if(col[i]==false && dig1[pos+i] ==false && dig2[i-pos+n]==false) {
                StringBuilder tmp = new StringBuilder(path.get(pos));
                tmp.setCharAt(i,'Q');
                path.remove(pos);
                path.add(pos,tmp.toString());//修改成Q
                col[i]=dig1[pos+i]=dig2[i-pos+n]=true;
                dfs(n,pos+1);//递归下一行
                //回溯
                StringBuilder tmp2 = new StringBuilder(path.get(pos));
                tmp2.setCharAt(i,'.');
                path.remove(pos);
                path.add(pos,tmp2.toString());//修改回.
                col[i]=dig1[pos+i]=dig2[i-pos+n]=false;
            }
        }
    }




}
